package doing.doing_501_1000;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 994. RottingOranges
 * <p>
 * 在给定的网格中，每个单元格可以有以下三个值之一：
 * 0-空单元格、1-鲜橘子、2-腐烂的橘子。
 * <p>
 * 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
 * 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
 * <p>
 * 示例 2：
 * 输入：[[2,1,1],
 * [0,1,1],
 * [1,0,1]]
 * 输出：-1
 * 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
 * <p>
 * 示例 3：
 * 输入：[[0,2]]
 * 输出：0
 * 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
 * <p>
 * 2019-03-24 9:33 AM
 **/
@Slf4j
public class RottingOranges {

    @SuppressWarnings("all")
    public int orangesRotting(int[][] grid) {
        int times = 0;

        // 腐烂队列，结构为：{x坐标，y坐标，年龄}
        Queue<int[]> rot = new LinkedList<>();

        int r = grid.length;
        int c = grid[0].length;

        // 遍历所有 2-(腐烂) 的节点，放到rot队列中
        // 顺序存储
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 2) {
                    // i是横坐标，j是纵坐标，0是年龄
                    rot.add(new int[]{i, j, 0});
                }
            }
        }

        int[][] direction = new int[][]{{0, 1},
                {0, -1},
                {1, 0},
                {-1, 0}};

        // 遍历所有腐烂的节点
        while (!rot.isEmpty()) {

            // 从队列头部, 出队列
            // 队列中是所有 2 - 腐烂节点
            int[] pre = rot.poll();

            times = pre[2];

            // 遍历腐烂节点, 四个方向
            for (int[] direct : direction) {

                //四方向中的一个方向，推算出坐标 x, y
                int x = pre[0] + direct[0];
                int y = pre[1] + direct[1];

                // 如果已经是1了，就晋升为2
                if (x >= 0 && x < r
                        && y >= 0 && y < c
                        && grid[x][y] == 1) {

                    // 晋升 1 -> 2 腐烂节点
                    grid[x][y] = 2;

                    //添加新的腐烂节点
                    rot.add(new int[]{x, y, pre[2] + 1});
                }
            }
        }

        // 如果仍有一个是1，说明无法被腐化，返回-1
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return times;
    }

    @Test
    public void test() {
        int[][] arr = new int[][]{{2, 1, 1},
                {0, 1, 1},
                {0, 0, 1}};
        log.info("result:{}", orangesRotting(arr));
    }

}




























/*
public int orangesRotting(int[][] grid) {
    Queue<int[]> rot = new LinkedList<>();
    int r = grid.length, c = grid[0].length;

    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            if (grid[i][j] == 2)
                rot.add(new int[]{i, j, 0});

    int res = 0;
    int[][] d = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    while (!rot.isEmpty()) {
        int[] pre = rot.poll();
        res = pre[2];
        for (int[] it : d) {
            int x = pre[0] + it[0];
            int y = pre[1] + it[1];
            if (x >= 0 && x < r && y >= 0 && y < c && grid[x][y] == 1) {
                grid[x][y] = 2;
                rot.add(new int[]{x, y, pre[2] + 1});
            }
        }
    }

    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            if (grid[i][j] == 1)
                return -1;

    return res;
}
*/
